//字符串压缩
/*字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
*/
class Solution {
public:
    string compressString(string S) {
        int count = 1;
        // old_char = S[0];
        string ret(1, S[0]);
        for (int i = 1; i < S.size(); i++) {
            if (S[i] == S[i - 1]) {
                count++;
            } else {
                ret += to_string(count);
                ret += S[i];
                count = 1;
            }
        }
        ret += to_string(count);
        if (ret.size() < S.size())
            return ret;
        return S;
    }
};


//字符串相乘
/*给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
*/
class Solution {
public:
    string add(string& num1, string& num2) {
        string sum;
        int count = 0;
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        while (i >= 0 || j >= 0 || count) {
            int temp = 0;
            if (i >= 0)
                temp += (num1[i] - '0');
            if (j >= 0)
                temp += (num2[j] - '0');
            temp += count;
            if (temp >= 10) {
                count = 1;
            } else {
                count = 0;
            }
            sum += ((temp % 10) + '0');
            i--;
            j--;
        }
        reverse(sum.begin(), sum.end());
        return sum;
    }
    string multiply(string num1, string num2) {
        if(num1[0]=='0'||num2[0]=='0')
        return "0";
        string ret("0");
        string new_num2 = num2;
        for (int i = num1.size() - 1; i >= 0; i--) {
            int temp = num1[i] - '0';
            while (temp) {
                ret = add(ret, new_num2);
                temp--;
            }
            new_num2 += '0';
        }
        return ret;
    }
};